package com.leecode.xiehf.page_02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0052 {

    public static void main(String[] args) {
        Solution_0052 solution = new Solution_0052();
        int s = solution.totalNQueens(4);
        System.out.println(s);
    }

    public int totalNQueens(int n) {
        return solve(n, 0, 0, 0, 0);
    }
    public int solve(int n, int row, int columns, int left, int right) {
        if (row == n) {
            return 1;
        }
        int count = 0;
        int availablePositions = ((1 << n) - 1) & (~(columns | left | right));
        while (availablePositions != 0) {
            int position = availablePositions & (-availablePositions);
            availablePositions = availablePositions & (availablePositions - 1);
            count += solve(n, row + 1, columns | position, (left | position) << 1, (right | position) >> 1);
        }
        return count;
    }

}
